package BinaryTree;

//二叉排序树的增删查改
public class BinarySearchTree {
    public static class Node {
        int key;
        Node left;
        Node right;
        public Node(int key) {
            this.key = key;
        }
    }
    private Node root = null;

    // 在搜索树中查找 key，如果找到，返回 key 所在的结点，否则返回 null
    public Node search(int key) {
        // wirte code here
        Node cur = root;
        while (cur != null) {
            if (cur.key > key) {
                cur = cur.left;
            } else if (cur.key < key) {
                cur = cur.right;
            } else {
                return cur;
            }
        }
        return null;
    }

    // 插入值为key的元素
    public boolean insert(int key) {
         // wirte code here
        if (root == null) {
            root = new Node(key);
            return true;
        }

        Node cur = root;
        Node parent = null;

        while (cur != null) {
            if (cur.key > key) {
                parent = cur;
                cur = cur.left;
            } else if (cur.key < key) {
                parent = cur;
                cur = cur.right;
            } else {
                return false; //节点重复
            }
        }

        Node newNode = new Node(key); //新建节点
        if (parent.key < key) {
            parent.right = newNode;
        } else if (parent.key > key) {
            parent.left = newNode;
        } else {
            return false;
        }
        return true;
    }

    // 删除值为key的元素
    public boolean remove(int key) {
        // wirte code here,主要分为三种情况
        Node parent = null;
        Node cur = root;//cur负责找到需要删除的节点
        while (cur != null) {
            if (cur.key < key) {
                parent = cur;
                cur = cur.right;
            } else if (cur.key > key) {
                parent = cur;
                cur = cur.left;
            } else {
                removeNode(parent, cur);
                return true;
            }
        }
        return false;
    }

    private void removeNode(Node parent, Node cur) {
        //至此，cur指向待删除的节点
        if (cur.left == null) {  //如果左孩子为空
            if (cur == root) {
                root = cur.right;
            } else if (parent.left == cur) {
                parent.left = cur.right;
            } else {
                parent.right = cur.right;
            }
        } else if (cur.right == null) {  //如果右孩子为空
            if (cur == root) {
                root = cur.left;
            } else if (parent.left == cur) {
                parent.left = cur.left;
            } else {
                parent.right = cur.left;
            }
        } else {  //如果左右孩子都不为空
            Node target = cur.right;//找到cur右子树中的最小节点，替换cur节点，并且删除这个最小节点
            Node targetParent = cur; //target节点的双亲结点
            while (target.left != null) {  //找到右子树的最小节点
                targetParent = target;
                target = target.left;
            }
            cur.key = target.key; //覆盖

            if (target == targetParent.left) {
                targetParent.left = target.right;
            } else {
                targetParent.right = target.right;
            }
        }
    }
}